package com.leetcode.algorithm.y19.m04;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import javafx.util.Pair;

/**
 * leetcode-cn.com
 * 
 * (done)394. 字符串解码
 * (done)733. 图像渲染
 * (done)542. 01 矩阵
 * (done)841. 钥匙和房间
 * @author: jie.deng
 * @time: 2019年4月10日 上午12:25:41
 */
public class MySolution0410 {
    
    /**
     * 394. 字符串解码
     * 
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     * 
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     * 
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     * 
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     * 
     * 示例:
     * 
     * s = "3[a]2[bc]", 返回 "aaabcbc".
     * s = "3[a2[c]]", 返回 "accaccacc".
     * s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
     * @param s
     * @return
     */
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        Stack<String> stack = new Stack<String>();
        char[] chs = s.toCharArray();
        int idx = 0;
        while (idx < chs.length) {
            // 遇到连续的数字，入栈
            // 遇到[，入栈
            // 遇到]，连续出栈直到[，然后出栈[、出栈数字，处理后将结果入栈
            // 其他，入栈
            char ch = chs[idx];
            if (ch == '[') {
                stack.push("[");
                idx++;
            } else if (ch == ']') {
                StringBuilder sbStr = new StringBuilder();
                String str = null;
                while (!stack.isEmpty() && !"[".equals(str = stack.pop())) {
                    sbStr.insert(0, str);
                }
                if (!stack.isEmpty()) {
                    str = stack.pop();
                    int num = Integer.parseInt(str);
                    str = sbStr.toString();
                    if (num > 0) {
                        num--;
                        while (num > 0) {
                            sbStr.append(str);
                            num--;
                        }
                        stack.push(sbStr.toString());
                    }
                }
                idx++;
            } else if (ch >= '1' && ch <= '9') {
                // 连续的数字，直至遇到非数字停止
                int fromIdx = idx;
                while (ch >= '0' && ch <= '9') {
                    idx++;
                    ch = chs[idx];
                }
                stack.push(new String(chs, fromIdx, idx - fromIdx).replaceFirst("^0+", ""));
            } else {
                // 其他，入栈
                stack.push("" + ch);
                idx++;
            }
        }
        StringBuilder ret = new StringBuilder();
        while (!stack.isEmpty()) {
            ret.insert(0, stack.pop());
        }
        return ret.toString();
    }
    
    /**
     * 733. 图像渲染
     * 
     * 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
     * 
     * 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
     * 
     * 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
     * 
     * 最后返回经过上色渲染后的图像。
     * 
     * 示例 1:
     * 
     * 输入: 
     * image = [[1,1,1],[1,1,0],[1,0,1]]
     * sr = 1, sc = 1, newColor = 2
     * 输出: [[2,2,2],[2,2,0],[2,0,1]]
     * 解析: 
     * 在图像的正中间，(坐标(sr,sc)=(1,1)),
     * 在路径上所有符合条件的像素点的颜色都被更改成2。
     * 注意，右下角的像素没有更改为2，
     * 因为它不是在上下左右四个方向上与初始点相连的像素点。
     * 注意:
     * 
     * image 和 image[0] 的长度在范围 [1, 50] 内。
     * 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
     * image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
     * @param image
     * @param sr
     * @param sc
     * @param newColor
     * @return
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int rows = image.length;
        int cols = image[0].length;
        Stack<Pair<Integer, Integer>> stack = new Stack<Pair<Integer, Integer>>();
        int color = image[sr][sc];
        if (color == newColor) {
            return image;
        }
        stack.push(new Pair<Integer, Integer>(sr, sc));
        while (!stack.isEmpty()) {
            Pair<Integer, Integer> pair = stack.pop();
            int row = pair.getKey();
            int col = pair.getValue();
            image[row][col] = newColor;
            // 上
            if (row - 1 >= 0 && image[row - 1][col] == color) {
                stack.push(new Pair<Integer, Integer>(row - 1, col));
            }
            // 下
            if (row + 1 < rows && image[row + 1][col] == color) {
                stack.push(new Pair<Integer, Integer>(row + 1, col));
            }
            // 左
            if (col - 1 >= 0 && image[row][col - 1] == color) {
                stack.push(new Pair<Integer, Integer>(row, col - 1));
            }
            // 右
            if (col + 1 < cols && image[row][col + 1] == color) {
                stack.push(new Pair<Integer, Integer>(row, col + 1));
            }
        }
        return image;
    }
    
    /**
     * 542. 01 矩阵
     * 
     * 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
     * 
     * 两个相邻元素间的距离为 1 。
     * 
     * 示例 1: 
     * 输入:
     * 
     * 0 0 0
     * 0 1 0
     * 0 0 0
     * 输出:
     * 
     * 0 0 0
     * 0 1 0
     * 0 0 0
     * 示例 2: 
     * 输入:
     * 
     * 0 0 0
     * 0 1 0
     * 1 1 1
     * 输出:
     * 
     * 0 0 0
     * 0 1 0
     * 1 2 1
     * 注意:
     * 
     * 给定矩阵的元素个数不超过 10000。
     * 给定矩阵中至少有一个元素是 0。
     * 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
     * @param matrix
     * @return
     */
    public int[][] updateMatrix(int[][] matrix) {
        // 从元素0出发，广度优先，逐层填充，直到遍历完所有元素
        // 另一种，从非0元素出发，广度优先，计算到0的最短路径
        int rows = matrix.length;
        int cols = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    // 非0
                    if (!(((i - 1) >= 0 && matrix[i - 1][j] == 0) 
                            || ((i + 1) < rows && matrix[i + 1][j] == 0)
                            || ((j - 1) >= 0 && matrix[i][j - 1] == 0) 
                            || ((j + 1) < cols && matrix[i][j + 1] == 0))) {
                        // 也没有邻居是0
                        bfs(matrix, i, j, rows, cols);
                    }
                }
            }
        }
        return matrix;
    }
    
    private void bfs(int[][] matrix, int r, int c, int rows, int cols) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList<Pair<Integer, Integer>>();
        Set<String> visitedSet = new HashSet<String>();
        queue.offer(new Pair<Integer, Integer>(r, c));
        visitedSet.add(r + "" + c);
        int dis = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Pair<Integer, Integer> pair = queue.poll();
                int row = pair.getKey();
                int col = pair.getValue();
                // 上
                if ((row - 1) >= 0) {
                    if (matrix[(row - 1)][col] == 0) {
                        matrix[r][c] = dis;
                        return;
                    } else {
                        if (!visitedSet.contains((row - 1) + "" + col)) {
                            visitedSet.add((row - 1) + "" + col);
                            queue.offer(new Pair<Integer, Integer>((row - 1), col));
                        }
                    }
                }
                // 下
                if ((row + 1) < rows) {
                    if (matrix[(row + 1)][col] == 0) {
                        matrix[r][c] = dis;
                        return;
                    } else {
                        if (!visitedSet.contains((row + 1) * cols + col)) {
                            visitedSet.add((row + 1) + "" + col);
                            queue.offer(new Pair<Integer, Integer>((row + 1), col));
                        }
                    }
                }
                // 左
                if ((col - 1) >= 0) {
                    if (matrix[row][(col - 1)] == 0) {
                        matrix[r][c] = dis;
                        return;
                    } else {
                        if (!visitedSet.contains(row * cols + (col - 1))) {
                            visitedSet.add(row + "" + (col - 1));
                            queue.offer(new Pair<Integer, Integer>(row, (col - 1)));
                        }
                    }
                }
                // 右
                if ((col + 1) < cols) {
                    if (matrix[row][(col + 1)] == 0) {
                        matrix[r][c] = dis;
                        return;
                    } else {
                        if (!visitedSet.contains(row * cols + (col + 1))) {
                            visitedSet.add(row + "" + (col + 1));
                            queue.offer(new Pair<Integer, Integer>(row, (col + 1)));
                        }
                    }
                }
            }
            dis++;
        }
    }

    /**
     * 841. 钥匙和房间
     * 
     * 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
     * 
     * 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
     * 
     * 最初，除 0 号房间外的其余所有房间都被锁住。
     * 
     * 你可以自由地在房间之间来回走动。
     * 
     * 如果能进入每个房间返回 true，否则返回 false。
     * 
     * 示例 1：
     * 
     * 输入: [[1],[2],[3],[]]
     * 输出: true
     * 解释:  
     * 我们从 0 号房间开始，拿到钥匙 1。
     * 之后我们去 1 号房间，拿到钥匙 2。
     * 然后我们去 2 号房间，拿到钥匙 3。
     * 最后我们去了 3 号房间。
     * 由于我们能够进入每个房间，我们返回 true。
     * 示例 2：
     * 
     * 输入：[[1,3],[3,0,1],[2],[0]]
     * 输出：false
     * 解释：我们不能进入 2 号房间。
     * 提示：
     * 
     * 1 <= rooms.length <= 1000
     * 0 <= rooms[i].length <= 1000
     * 所有房间中的钥匙数量总计不超过 3000。
     * @param rooms
     * @return
     */
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] visited = new boolean[rooms.size()];
        queue.offer(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int num = queue.poll();
            List<Integer> list = rooms.get(num);
            for (Integer idx : list) {
                if (!visited[idx]) {
                    queue.offer(idx);
                    visited[idx] = true;
                }
            }
        }
        for (boolean flag : visited) {
            if (!flag) {
                return false;
            }
        }
        return true;
    }
}
